package com.cfwx.datastructure.sort;

/**
 * 冒泡排序
         分析
       因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，
        而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。
        若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，
        因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量exchange，
        在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。
        各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。
*
*/
public class BubbleSort {

	/**
	 * 对r数组中的无序数据进行排序
	 * @param r
	 */
	public void MyBulleSort(int[] r){
		Boolean exchange;
		int i,j;
		int n=r.length-1;
		System.out.println("最多进行"+n+"趟排序");
		for( i=0;i<n;i++){//外循环有n-1趟
			exchange = false;
			for(j=n-1;j>=i;j--){//内循环对当前无序区r[i..n]自下向上扫描
				if(r[j+1]<r[j]){
					int temp = r[j+1];
					r[j+1]=r[j];
					r[j]=temp;
					exchange = true;
				}
			}
//			for(j=0;j<n-i;j++){//内循环对当前无序区r[i..n]自上向下扫描
//				if(r[j+1]<r[j]){
//					int temp = r[j];
//					r[j]=r[j+1];
//					r[j+1]=temp;
//					exchange = true;
//				}
//			}
			if(!exchange){//本趟排序未发生交换，提前终止算法
				break;
			}
			int index = i+1;
			System.out.print("第"+index+"趟排序为：");
			for(int k=0;k<r.length;k++){
				System.out.print(r[k]+" ");
			}
			System.out.println();
		}
		

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] mySeq ={11,888,33,129,66,4,34,123,345,3,1};
		BubbleSort bs = new BubbleSort();
		bs.MyBulleSort(mySeq);
	}

}
